class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if (nums.size() < 4) return result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size() - 3; k++) {
            if (nums[k] > 0 && target > 0 && nums[k] > target) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            for (int i = k + 1; i < nums.size() - 2; i++) {
                if (nums[k] + nums[i] > 0 && target > 0 && nums[k]+nums[i] > target) break;
                if (i > k + 1 && nums[i] == nums[i - 1]) continue;
                int left = i + 1, right = nums.size() - 1;
                while (left < right) {
                    long long val = nums[k] + nums[i];
                    val += nums[left] + nums[right];
                    if (val > target) right--;
                    else if (val < target) left++;
                    else {
                        result.push_back({nums[k], nums[i], nums[left], nums[right]});
                        left++, right--;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                    }
                }
            }
        }
        return result;
    }
};
